package 力扣面试经典150;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-03-17
 * Time:16:09
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 力扣面试经典150:57. 插入区间
 * 中等
 * 相关标签
 * 相关企业
 * 给你一个 无重叠的 ，按照区间起始端点排序的区间列表。
 * 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
 * 示例 1：
 * 输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
 * 输出：[[1,5],[6,9]]
 */
public class insert {
    public static void main(String[] args) {
        insert(new int[][]{{1,3},{6,9}},new int[]{2,5});
    }
    public static int[][] insert(int[][] intervals, int[] newInterval) {
        //l表示newInterval 第一个数，R表示第二个数
        int L = newInterval[0], R = newInterval[1], n = intervals.length, index = 0;
        List<int[]> ans = new ArrayList<>();
        //while 循环直到在 intervals 数组中找到含有 newInterval 中的数的位置，在此之前的数组直接add就行
        while(index < n && intervals[index][1] < L) {
            ans.add(intervals[index++]);
        }
        //while 循环跳过包含或者被包含的数组
        while(index < n && intervals[index][0] <= R){
            L = Math.min(L, intervals[index][0]);
            R = Math.max(intervals[index++][1], R);
        }
        //添加包含或被包含的数组
        ans.add(new int[]{L, R});
        //后续只需要while 循环add就行了
        while(index < n) ans.add(intervals[index++]);
        return ans.toArray(new int[ans.size()][]);
    }
}
